from entity import grammar, tool


# 创建一个 Grammar 对象来表示当前文法，并将该对象添加到 graList 列表中
# 将该文法映射到 graList 列表中的索引，即将 tempGra 添加到 graOrder 字典中
# 将该文法添加到以左部符号为键的列表中
def getGras(filename='../resources/setGrammar.txt'):
    graList = []
    graOrder = {}
    graMap = {}
    order = 0
    with open(filename, 'r') as f:
        for gra in f.readlines():
            curGra = gra.replace('\n', '').replace(' ', '').replace('<', '<').replace('\t', '').split('→')
            tempGra = grammar.Grammar(curGra[0], curGra[1])
            graList.append(tempGra)
            graOrder[tempGra] = order
            if graMap.get(curGra[0]) is None:
                graMap[curGra[0]] = []
            graMap[curGra[0]].append(tempGra)
            order += 1

    # graList：包含所有文法的列表
    # graOrder：将每个文法映射到其在graList列表中的索引
    # graMap：将每个左部符号映射到一个包含所有以该符号为左部的文法的列表中
    return graList, graOrder, graMap


# 递归的判断非终结符是否可以为空
# 首先判断该非终结符是否为终结符
#   如果不是，则遍历以该非终结符为左部的所有文法，分别检查它们的右部是否可以为空
#       如果右部存在不可为空的符号，则继续检查下一个文法
# 所有文法都遍历完了，仍然没有找到可为空的右部，则该非终结符不可为空
def isEpsilon(unTerm, graMap):
    # 终结符必然不能为空
    if unTerm[0] != '<':
        return False
    # 拿到非终结符为左部的文法列表
    items = graMap[unTerm]
    # 遍历每条文法
    for item in items:
        rights = item.getRight()
        # 如果直接导出空
        if len(rights) == 0:
            # 可空
            return True
        # 查看右边的每一个符号
        for right in rights:

            # 防止循环检查
            if right == unTerm:
                continue
            # 遇到终结符必然不可能为空
            if right[0] != '<':
                # return False
                break
            else:
                # 如果这个非终结符不能为空
                if not isEpsilon(right, graMap):
                    break
        # 每个符号都可以为空
        else:
            return True
    return False


# 计算非终结符的First集合
# 遍历所有非终结符，并对每个非终结符计算FIRST集合
# 如果该非终结符还没有FIRST集合信息，则初始化一个空集合
# 遍历以该该非终结符为左部的所有产生式中的所有符号，并将每个符号加入该非终结符的FIRST集合中
# 单独处理可产生空串的情况
def firstFirst(gras, firsts, graMap):
    # 遍历所有非终结符
    for gra in gras:
        # 得到左部的非终结符
        unTerm = gra.getLeft();
        # 跳过S
        if unTerm == 'S':
            continue
        # 还没有信息则初始化集合
        if firsts.get(unTerm) is None:
            firsts[unTerm] = set()
        # 得到文法右部符号串
        rights = gra.getRight()

        # 处理epsilon
        # 如果该产生式为空串，将ε加入该非终结符的FIRST集合中
        # 如果该非终结符本身可以推导为空串，则也将ε加入该非终结符的FIRST集合中。
        if len(rights) == 0:
            firsts[unTerm].add('e')
        if isEpsilon(unTerm, graMap):
            firsts[unTerm].add('e')

        for right in rights:
            # 加进去
            firsts[unTerm].add(right)
            # 如果不能为空退出
            if not isEpsilon(right, graMap):
                break


# 集合里有非终结符
def hasUnTerm(symSet):
    symList = list(symSet)
    for s in symList:
        if s[0] == '<':
            return True
    return False


# 二次计算First集合
# 把非终结符的First集合合并
def firstSecond(unTerms, firsts):
    ufSet = set()
    fSet = set()

    for unTerm in unTerms:
        if hasUnTerm(firsts[unTerm]):
            ufSet.add(unTerm)
        else:
            fSet.add(unTerm)
            
    # 在while循环中，先遍历fSet中的每个元素f，再遍历ufSet中的每个元素u
    # 如果u对应的First集合中包含f，则将f从u的First集合中删除
    # 将u和f的First集合合并
    # 如果合并后的集合中含有ε，则保留ε
    # 如果u的First集合中不含有非终结符，则将u从ufSet中删除，加入到fSet中
    while len(ufSet) > 0:
        # 遍历fSet中的每一个元素f
        fList = list(fSet)
        for f in fList:
            # 遍历ufSet中每一个元素u
            uList = list(ufSet)
            for u in uList:
                # 首先要删除等于自身的项目，防止无限循环
                if u in firsts[u]:
                    firsts[u].remove(u)
                # 如果u对应的first集合包含f
                if f in firsts[u]:
                    # 把f从u的First中删除
                    firsts[u].remove(f)
                    # 是否移除合并后的epsilon
                    noEps = False
                    # 注意对epsilon的处理，e在u中不在f中
                    if 'e' in firsts[f] and (not 'e' in firsts[u]):
                        noEps = True
                    # 把u和f对应的first集合合并
                    firsts[u] |= firsts[f]

                    if noEps:
                        # 移除
                        firsts[u].remove('e')

                # 如果u全为非终结符
                if not hasUnTerm(firsts[u]):
                    # 从ufSet删除u，将u加入fSet
                    ufSet.remove(u)
                    fSet.add(u)


# 初次计算文法的Follow集合
# 对于每个非终结符，初始化follow集为空，检查所有的文法
#   如果一个文法的右部包含该非终结符，则将该非终结符的Follow集合加入该文法右部中该非终结符后面的符号的First集合中
# 如果该符号的First集合包含epsilon，则继续将下一个符号的First集合加入该Follow集合中，直到没有epsilon元素为止
# 如果该非终结符是文法的最后一个符号，则将文法左部的非终结符加入该非终结符的Follow集合中
# 如果该非终结符是文法的第一个符号，则将该文法左部的非终结符加入该非终结符的Follow集合中
def followFirst(unTerms, gras, follows, firsts, graMap):
    dbStr = ''
    # 遍历所有非终结符
    for unTerm in unTerms:
        if unTerm == dbStr:
            print('处理%s' % unTerm)
        # 如果没有添加过这个follow
        if follows.get(unTerm) is None:
            # 初始化
            follows[unTerm] = set()
            # 遍历所有文法
        for gra in gras:
            if unTerm == dbStr:
                print('当前文法为%s' % str(gra))
            left = gra.getLeft()
            rights = gra.getRight()
            # 加入first集合标志
            add = False
            # 遍历文法右部符号
            for right in rights:
                if unTerm == dbStr:
                    print(right)
                # 需要加入了
                if add:
                    if unTerm == dbStr:
                        print('加入%s' % right)
                    # 非终结符取并集
                    if right[0] == '<':
                        # 加到集合去
                        follows[unTerm] |= firsts[right]
                    # 终结符添加
                    else:
                        follows[unTerm].add(right)
                # 如果发现了unTerm
                if right == unTerm:
                    if unTerm == dbStr:
                        print('发现%s' % right)
                    # 需要将后面的都first加入follow
                    add = True
                # 如果发现了障碍，右部follow结束
                if right != unTerm and add and (not isEpsilon(right, graMap)):
                    break
            else:
                if add and left != unTerm:
                    follows[unTerm].add(left)


# 对follow集合的第二次处理
# 遍历所有非终结符的follow集合，将follow集合分为包含非终结符和不包含非终结符两个集合
# 对于不包含非终结符的集合，遍历每一个元素f，然后遍历包含非终结符的集合中的每一个元素u，进行相应的处理
#   如果u对应的follow集合包含f，就把f从u的First中删除，并把u和f对应的first集合合并
#   如果u的follow集合中没有包含非终结符的元素，就将u从包含非终结符的集合中删除，并将u加入不包含非终结符的集合中
def followSecond(follows, unTerms):
    # 把集合分为first里含有非终结符和没有非终结符 ufSet,fSet两个集合
    ufSet = set()
    fSet = set()

    for unTerm in unTerms:
        if hasUnTerm(follows[unTerm]):
            ufSet.add(unTerm)
        else:
            fSet.add(unTerm)
    # 遍历fSet中的每一个元素f
    fList = list(fSet)
    for f in fList:
        # 遍历ufSet中每一个元素u
        uList = list(ufSet)
        for u in uList:
            # 首先要删除等于自身的项目，防止无限循环
            if u in follows[u]:
                follows[u].remove(u)
            # 如果u对应的follow集合包含f
            if f in follows[u]:
                # 把f从u的First中删除
                follows[u].remove(f)
                # 把u和f对应的first集合合并
                follows[u] |= follows[f];

            # 如果u全为非终结符
            if not hasUnTerm(follows[u]):
                # 从ufSet删除u，将u加入fSet
                ufSet.remove(u)
                fSet.add(u)
                # 代入相消
    uList = list(ufSet)
    # 遍历每一个含有非终结符的follow
    for unTerm in uList:
        # 遍历非终结符的每一个元素
        for u in ufSet:
            # 如果u的follow集包含unTerm
            if unTerm in follows[u]:
                # 把u的Follow集与unTerm的follow集合并，去除和左部相同的元素
                follows[u] |= follows[unTerm]
                if u in follows[u]:
                    follows[u].remove(u);
                if unTerm in follows[u]:
                    follows[u].remove(unTerm);
    # 移除epsilon
    for unTerm in unTerms:
        if 'e' in follows[unTerm]:
            follows[unTerm].remove('e')
        if 'S' in follows[unTerm]:
            follows[unTerm].remove('S')


def getAllSymble(gras):
    title = tool.title
    # title = ['integer', 'float', 'procedure', 'begin', 'end', 'ood', 'if', 'then',
    #          'while', 'do', 'call', '#', ':=', '=', '(', ')', ';', ',', '.', 'id', 'un', 're', 'mn',
    #          'td']

    unTerms = set()
    for gra in gras:
        unTerms.add(gra.getLeft())
    unTerms.remove('S')
    title += list(unTerms)
    return title


# 得到First和Follow集合
def firstAndFollow(gras, graMap):
    # 首先计算所有非终结符
    unTerms = set()
    for gra in gras:
        unTerms.add(gra.getLeft())
    # 不需要开始符号
    unTerms.remove('S')

    # 计算所有first
    firsts = {}
    # 把终结符和first(非终结符)加到终结符里面去
    firstFirst(gras, firsts, graMap)
    # 合并非终结符
    firstSecond(unTerms, firsts)
    # first集合计算完成，打印检验

    # 计算Follow集
    follows = {'<程序>': {'#'}}

    # 右部follow和守门员福利
    followFirst(unTerms, gras, follows, firsts, graMap)
    # 替换非终结符
    followSecond(follows, unTerms)

    # follow集合计算完成，打印检验
    return firsts, follows


if __name__ == '__main__':
    l, o, m = getGras()
